#ifndef _LINKLIST_H
#include "stdio.h"
#include "stdlib.h"
#include "assert.h"
typedef int SLTDateType;
typedef struct SListNode
{
    SLTDateType data;
    struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);

//实现函数
SListNode* BuySListNode(SLTDateType x)
{
    SListNode* new=(SListNode*) malloc(sizeof (SListNode));
    //检查malloc是否成功
    if(new==NULL)
    {
        perror("malloc error");
        return NULL;
    }
    new->data=x;
    new->next=NULL;
    return new;
}

void SListPrint(SListNode* plist)// 单链表打印
{
    SListNode *pl=plist;//pl指向链表头节点
    while (pl!=NULL)//直到pl指向NULL结束
    {
        printf("%d->",pl->data);
        pl=pl->next;//将pl后移向下一个节点
    }
    printf("NULL\n");
}

void SListPushFront(SListNode** pplist, SLTDateType x)// 单链表的头插
{
    //开辟一个新节点new
    SListNode* new= BuySListNode(x);
    new->next=*pplist;//pplist是指向（指向链表头节点的指针）的指针，相当于new->next指向头节点
    *pplist=new;//重新指向新的头节点
}

void SListPushBack(SListNode** pplist, SLTDateType x)// 单链表尾插
{
    SListNode *new= BuySListNode(x);
    //链表为空
    if(*pplist==NULL)
    {
        *pplist=new;
    }
    else//非空
    {
        //找到链表尾
        SListNode *tail = *pplist;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = new;
    }
}

void SListPopBack(SListNode** pplist)// 单链表的尾删
{
    if(*pplist==NULL)//如果链表为空，直接返回
    {
        perror("SList is empty");
        return;
    }
    //找到尾节点tail和尾节点前驱pretail
    SListNode *tail=*pplist;
    SListNode *pretail=NULL;
    while (tail->next!=NULL)
    {
        pretail=tail;
        tail=tail->next;
    }
    free(tail);//释放尾节点
    if(pretail==NULL)//说明只有一个节点
        *pplist=NULL;
    else//至少两个节点
        pretail->next=NULL;//删除尾节点后，我们就能正确地更新链表的状态，避免产生野指针
}

void SListPopFront(SListNode** pplist)// 单链表头删
{
    if(*pplist==NULL)//如果链表为空，直接返回
    {
        perror("SList is empty");
        return;
    }
    //头节点没删之前，newhead指向头节点下一个节点
    //删除头节点，再让原先指向被删除头节点的指针指向新头节点(*newhead)
    SListNode *newhead=(*pplist)->next;
    free(*pplist);
    *pplist=newhead;
}

SListNode* SListFind(SListNode* plist, SLTDateType x)// 单链表查找
{
    SListNode *target=plist;//节点指针target遍历链表
    while (target)
    {
        if(target->data==x)
            return target;
        target=target->next;
    }
    //走到这里说明没找到
    printf("%d Not Found\n",x);
    return NULL;
}

void SListInsertAfter(SListNode* pos, SLTDateType x)// 单链表在pos位置之后插入x
{
    assert(pos);
    SListNode *new= BuySListNode(x);
    new->next=pos->next;
    pos->next=new;
}

void SListEraseAfter(SListNode* pos)//单链表删除pos位置之后的值
{
    assert(pos&&pos->next);

    SListNode* tmp=pos->next;
    pos->next=tmp->next;
    free(tmp);
}

void SListDestroy(SListNode* plist)// 单链表的销毁
{
    SListNode* tmp=plist;
    //释放链表所有的节点
    while (plist!=NULL)
    {
        plist=tmp->next;
        free(tmp);
        tmp=plist;
    }
}
#endif //链表的插入_LINKLIST_H
